package LinkedList;

public class p面试题链表相交 {
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    public class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            if(headA == null || headB == null){
                return null;
            }
            ListNode a = headA;
            int lenA = 0;
            ListNode b = headB;
            int lenB = 0;
            while(a.next != null){
                a = a.next;
                lenA++;
            }
            while(b.next != null){
                b = b.next;
                lenB++;
            }
            a = headA;
            b = headB;
            if(lenA - lenB > 0){
                for(int i = 0; i < lenA - lenB; i++){
                    a = a.next;
                }
                while(a != null){
                    if(a == b){
                        return a;
                    }
                    a = a.next;
                    b = b.next;
                }
            } else {
                for(int i = 0; i < lenB - lenA; i++){
                    b = b.next;
                }
                while(a != null){
                    if(a == b){
                        return a;
                    }
                    a = a.next;
                    b = b.next;
                }
            }
            return null;
        }
    }
}
